Cours 2.11.1 du Mastère de Recherches en Informatique
Algorithmes avancés - Nicolas Schabanel
Cours n°4 - Partie B/C
Introduction à la programmation semi-définie
• De la formulation quadratique d'un problème à la formulation sous forme d'un programme vectoriel
• Technique d'arrondi : Couper suivant un hyperplan pour Max-Cut
• Une O(n^1/3)-approximation pour le coloriage de graphes 3-colorables
TD n°4
• Tirage d'un vecteur unitaire aléatoire uniforme
• Une O(n^1/4)-approximation pour le coloriage de graphes 3-coloriables
